I would like to propose an improvement in the Hashmap solution. Instead of traversing the hash maps of the first vector, choose the one with minimum length min(v1.keySet().length, v2.keySet().length)

I got this question at my FB onsite in August 2020. The interviewer did not accept my hashmap solution. He told me that hashing/lookups, while on surface look efficient, for large sparse vectors, hashing function takes up bulk of the computation that we might be better off with the first method. Wihile proposing hashmap/set solutions, take a minute to think about the complexity hashing function.

Am I the only one didn't get the point of the medium level tag?

Perf vs Efficiency

Has anyone found an algorithm that is both performant and Facebook-approved?
The "non-efficient array approach" performed best.
JavaScript Map, Object and Set performed horribly.
I did get a "tuple" (array of [index, value]) to perform a little better, 30% slower than array.
Using Array.reduce or switching to the smaller size collection made runtime worse.

// ARRAY
// Runtime: 100 ms, faster than 98.92%
// Memory Usage: 51 MB, less than 95.04%
function SparseVector(nums) {
  return {
    nums,
    dotProduct: function(vec) {
      let d = 0

      for (let i = 0; i < vec.nums.length; i++) {
        if (this.nums[i] && vec.nums[i]) d += this.nums[i] * vec.nums[i]
      }
      return d;
    }
  };
}

// "TUPLE"
// Runtime: 132 ms, faster than 42.89%
// Memory Usage: 53.4 MB, less than 62.50%
class SparseVector {

  constructor(nums) {
    this.nums = [...nums.entries()].filter(el => el[1] !== 0);
  }

  dotProduct(vec) {
    let d = 0;
    for(let [index, value] of vec.nums){
      let num = this.nums.find(el => el[0] === index);
      if(num) d += value * num[1];
    }
    return d;
  }
}

// MAP
// 396 ms, faster than 5.17%
// Memory Usage: 71.3 MB, less than 5.17%
class SparseVector {

  constructor(nums) {
    this.nums = new Map([...nums.entries()].filter(el => el[1] !== 0));
  }

  dotProduct(vec) {
    let d = 0;
    this.nums.forEach((el, i) => {
      if (vec.nums.has(i)) d += vec.nums.get(i) * el;
    });
    return d;
  }
}

// OBJECT
// Runtime: 160 ms
// Memory Usage: 56.7 MB
function SparseVector(nums) {
  return {
    nums: nums.reduce((acc, el, i) => {
      if(el !== 0) acc[i] = el;
      return acc;
    }, {}),
    has: function(i){
      return this.nums.hasOwnProperty(i);
    }, 
    dotProduct: function(vec) {
      let d = 0;
      
      for (let [i, v] of Object.entries(vec.nums)) {
        if(this.has(i)) d += this.nums[i] * v;
      }
      return d;
    }
  };
}

This should be easy.

For approach #1, we could optimize by continuing the loop when either of the array has a 0 (no need to calculate the product)

I read the comments about FB onsite not accepting the hashmap solution. Could using linked lists be an additional option? I think it's the same time/space as these other solutions, but easier to code.

When you create the spare vector, iterate and generate a linked list of values != 0. Each node tracks its idx and val. That's O(N) time O(L) space to create the vectors.

For dot product, iterate over each linked list with a pointer. If the idx values don't match, move up the pointer with the lower idx value etc. It's O(min(L1, L2)) time O(1) space to calculate dot product. Now you don't have to worry about which linked list is shorter - you just stop when you reach the end of one of them.

My solution came at the bottom of time/space, but posting here anyway:

class VectorNode:
    def __init__(self, idx, val):
        self.idx = idx
        self.val = val
        self.next = None

class SparseVector:
    def __init__(self, nums: List[int]):
        self.list = None
        curr = None

        for idx, val in enumerate(nums):
            if val != 0:
                node = VectorNode(idx, val)
                if not self.list:
                    self.list = node
                    curr = node
                else:
                    curr.next = node
                    curr = node

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        left = self.list
        right = vec.list

        total = 0
        while left and right:
            if left.idx == right.idx:
                total += (left.val * right.val)
                left = left.next
                right = right.next
            elif left.idx < right.idx:
                left = left.next
            else:
                right = right.next

        return total

Love the Hashmap way, nice and clean

The question doesn't make sense. There needs to be some practical use of such an approach. There's no better/worst solution in normal use case.

class SparseVector:
    def __init__(self, nums: List[int]):
        # Time: O(M), Space: O(M) where M is the length of the vector
        self.vector =  {}
        for idx, num in enumerate(nums):
            if num!=0:
                self.vector[idx] = num

    # Return the dotProduct of two sparse vectors
    def dotProductNormal(self, vec: 'SparseVector') -> int:
        # Time: O(M)
        prod = 0
        for idx,val in self.vector.items():
            if idx in vec.vector:
                prod += val * vec.vector[idx]
        
        return prod
    
    # Return the dotProduct of two sparse vectors
    # when only one of them is sparse
    def dotProductFollowUp(self, vec: 'SparseVector') -> int:
        # Time: O(min(M,N)) where M and N are length of the two vectors
        prod = 0
        vec1, vec2 = sorted([self,vec],key = lambda x: len(x.vector))
        # iterate through the sparse one, whichever has smaller length
        for idx,val in vec1.vector.items():
            if idx in vec2.vector:
                prod += val * vec2.vector[idx]
        
        return prod
    
    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        # return self.dotProductNormal(vec)
        return self.dotProductFollowUp(vec)